#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std;
//int monthday[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//void Getdate(int y, int n)
//{
//	int year=0, month=0, day=0;
//	year = y;
//	int tmp = 0;
//	for (int i = 1; i <=12; i++)
//	{
//		tmp += monthday[i];
//		if (i == 2 && ((year % 4 == 0 && 4 % 100 != 0) || year % 400 == 0))
//			tmp++;
//		if (tmp >= n)
//		{
//			month = i;
//			day = n - (tmp - monthday[i]);
//			break;
//		}
//	}
//	cout << year << '-';
//	printf("%02d-", month);
//	printf("%02d", day);
//	cout << endl;
////}
//void Adddate(int y, int m,int d,int n)
//{
//	d += n;
//	for (int i = m; i <= 12; i++)
//	{
//		d -= monthday[i];
//		if (i == 2 && ((y % 4 == 0 && 4 % 100 != 0) || y % 400 == 0))
//			d--;
//		if (d <= 0) {
//			m = i;
//			d += monthday[i];
//			if (i == 2 && ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0))
//				d++;
//			break;
//		}
//	}
//	cout << y << '-';
//	printf("%02d-", m);
//	printf("%02d", d);
//	cout << endl;
//}
//int main()
//{
//	int y, m,d,n;
//	while(cin >> y >> m>>d>>n)
//	Adddate(y, m,d,n);
//	return 0;
//}
//bool col[9][10], row[9][10], grid[3][3][10];
//bool isValidSudoku(vector<vector<char>>& board) {
//	for (int i = 0; i < 9; i++)
//	{
//		for (int j = 0; j < 9; j++)
//		{
//			if (board[i][j] != '.')
//			{
//				int num = board[i][j] - '0';
//				if (row[i][num] == true || col[j][num] == true ||
//					grid[i / 3][j / 3][num] == true)
//					return false;
//				row[i][num] = true;
//				col[j][num] = true;
//				grid[i / 3][j / 3][num] = true;
//			}
//		}
//	}
//	return true;
//}
//bool row[9][10], col[9][10], grid[3][3][10];
//bool dfs(vector<vector<char>>& board)
//{
//	for (int i = 0; i < 9; i++)
//	{
//		for (int j = 0; j < 9; j++)
//		{
//			if (board[i][j] == '.')
//			{
//				for (int m = 1; m < 10; m++)
//				{
//					int num = board[i][j] - '0';
//					if (row[i][num] == false && col[j][num] == false &&
//						grid[i / 3][j / 3][num] == false)
//					{
//						board[i][j] = '0' + m;
//						row[i][num] = true;
//						col[j][num] = true;
//						grid[i / 3][j / 3][num] = true;
//						if (dfs(board) == true) return true;
//						board[i][j] = '.';
//						row[i][num] = false;
//						col[j][num] = false;
//						grid[i / 3][j / 3][num] = false;
//					}
//				}
//				return false;
//			}
//		}
//	}
//	return true;
//}
//void solveSudoku(vector<vector<char>>& board) {
//	for (int i = 0; i < 9; i++)
//	{
//		for (int j = 0; j < 9; j++)
//		{
//			if (board[i][j] != '.')
//			{
//				int num = board[i][j] - '0';
//				row[i][num] = true;
//				col[j][num] = true;
//				grid[i / 3][j / 3][num] = true;
//			}
//		}
//	}
//	dfs(board);
//}
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//int m, n;
//vector<vector<char>> visited;
//bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos)
//{
//	if (pos == word.size())
//	{
//		return true;
//	}
//	for (int k = 0; k < 4; k++)
//	{
//		int x = i + dx[k];
//		int y = j + dy[k];
//		if (x >= 0 && x < n && y >= 0 && y < m &&
//			visited[x][y] == false&& board[x][y]==word[pos])
//		{
//			visited[x][y] = true;
//			if (dfs(board, x, y, word, pos + 1)) return true;
//			visited[x][y] = false;
//		}
//	}
//	return false;
//}
//bool exist(vector<vector<char>>& board, string word) {
//	m = board.size(), n = board[0].size();
//	visited.resize(m);
//	for (int i = 0; i < m; i++)
//		visited[i].resize(n);
//	for (int i = 0; i < m; i++)
//	{
//		for (int j = 0; j < n; j++)
//		{
//			if (board[i][j] == word[0])
//			{
//				if (dfs(board,i,j,word,0)) return true;
//			}
//		}
//	}
//	return false;
//}
//int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
//int m, n;
//int ret;
//vector<vector<bool>> visited;
//void dfs(vector<vector<int>>& grid,int i,int j,int count)
//{
//	ret = max(ret, count);
//	for (int k = 0; k < 4; k++)
//	{
//		int x = i + dx[k], y = j + dy[k];
//		if (x >= 0 && x < m && y >= 0 && y < n &&
//			visited[x][y] == false)
//		{
//			visited[x][y] = true;
//			dfs(grid, x, y, count + grid[x][y]);
//			visited[x][y] = false;
//		}
//	}
//}
//int getMaximumGold(vector<vector<int>>& grid) {
//	m = grid.size(), n = grid[0].size();
//	visited.resize(m, vector<bool>(n));
//	for (int i = 0; i < m; i++)
//	{
//		for (int j = 0; j < n; j++)
//		{
//			if (grid[i][j])
//			{
//				visited[i][j] = true;
//				dfs(grid, i, j, grid[i][j]);
//				visited[i][j] = false;
//			}
//		}
//	}
//	return ret;
//}
vector<vector<bool>> visited;
int m, n;
int ret,cou=0;
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
void dfs(vector<vector<int>>& grid,int i,int j,int path)
{
	if (grid[i][j] == 2 )
	{
		if(path == cou)ret++;
		return;
	}
	for (int k = 0; k < 4; k++)
	{
		int x = i + dx[k], y = j + dy[k];
		if (x >= 0 && x < m && y >= 0 && y < n &&
			visited[x][y] == false && grid[x][y] == 0)
		{
			visited[x][y] = true;
			dfs(grid, x, y, path + 1);
			visited[x][y] = false;
		}
	}
}
int uniquePathsIII(vector<vector<int>>& grid) {
	m = grid.size(), n = grid[0].size();
	visited.resize(m, vector<bool>(n));
	int starti, startj;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (grid[i][j] == 0) cou++;
			if (grid[i][j] == 1)
				starti=i, startj=j;
		}
	}
	dfs(grid, starti, startj, 0);
	return ret;
}